#include "stdio.h"
#include "stdlib.h"

int ex_gcd(int e, int m, int *d, int *y)
{ // 函数返回gcd(a, b)
    if (m == 0)
    {
        *d = 1, *y = 0;
        return a;
    }
    int r = ex_gcd(b, a % b, y, x);
    *y -= (a / b) * (*x);
    return r;
}

int main()
{
    int a, b, x, y;
    cin >> a >> b;                                                    // 求a关于模b的逆元
    cout << (ex_gcd(a, b, x, y) == 1 ? (x % b + b) % b : -1) << endl; // -1表示逆元不存在

    return 0;
}